//
// Created by 86138 on 2025/6/15.
//
#include <iostream>
#include "BiTree.h"

using namespace std;

namespace sweetcookie6_1 {
    void InitLinkStack(LinkStack &S) {
        S = nullptr;
    }

    void DestroyLinkStack(LinkStack &S) {
        StackNode *p;
        while (S) {
            p = S;
            free(p);
            S = S->Next;
        }
        S = nullptr;
    }

    Status Push(LinkStack &S, SElemType e) {
        StackNode *p = (StackNode *) malloc(sizeof(StackNode));
        if (!p) exit(OVERFLOW);
        p->Data = e;
        p->Next = S;
        S = p;
        return OK;
    }

    Status Pop(LinkStack &S, SElemType &e) {
        if (S == nullptr) {
            printf("栈空，不能出栈\n");
            return ERROR;
        }
        StackNode *p = S;
        e = p->Data;
        S = S->Next;
        free(p);
        return OK;
    }

    bool StackEmpty(LinkStack S) {
        return S == nullptr;
    }

    void InitQueue(SqQueue &Q) {
        Q.base = (QElemType *) malloc(MAX_QSIZE * sizeof (QElemType));
        if (!Q.base) exit(OVERFLOW);
        Q.front = Q.rear = 0;
    }

    void DestroyQueue(SqQueue &Q) {
        if (Q.base) {
            free(Q.base);
        }
        Q.base = nullptr;
    }

    int QueueLength(SqQueue Q) {
        return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
    }

    bool QueueEmpty(SqQueue Q) {
        return Q.front == Q.rear;
    }

    Status EnQueue(SqQueue &Q, QElemType e) {
        if ((Q.rear + 1) % MAX_QSIZE == Q.front) {
            printf("队列已满，不能入队元素%d\n", e);
            return ERROR;
        }
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MAX_QSIZE;
        return OK;
    }

    Status DeQueue(SqQueue &Q, QElemType &e) {
        if (Q.front == Q.rear) {
            printf("队列空，不能出队元素%d\n", e);
            return ERROR;
        }
        e = Q.base[Q.front];
        Q.front = (Q.front + 1) % MAX_QSIZE;
        return OK;
    }

    void InitBiTree(BiTree &T) {
        T = nullptr;
    }

    void DestroyBiTree(BiTree &T) {
        if (!T) {
            return;
        }
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        free(T);
        T = nullptr;
    }

    Status InOrderTraverseNoRecur(BiTree T) {
        BiTNode *p, *q;
        p = T;
        LinkStack S;
        InitLinkStack(S);

        while (p || !StackEmpty(S)) {
            if (p) {
                Push(S, p);
                p = p->lchild;
            } else {
                Pop(S, q);
                cout << q->data << " ";
                p = q->rchild;
            }
        }
        cout << endl;
        DestroyLinkStack(S);

        return OK;
    }

    Status PreOrderTraverseNoRecur(BiTree T) {
        BiTNode *p, *q;
        LinkStack S;
        InitLinkStack(S);

        Push(S, T);
        while (!StackEmpty(S)) {
            Pop(S, q);
            cout << q->data << " ";
            if (q->rchild) {
                Push(S, q->rchild);
            }
            if (q->lchild) {
                Push(S, q->lchild);
            }
        }
        DestroyLinkStack(S);
        cout << endl;
        return OK;
    }

    Status LevelOrderTraverse(BiTree T) {
        SqQueue Q;
        InitQueue(Q);
        BiTNode *q;
        EnQueue(Q, T);
        while (!QueueEmpty(Q)) {
            DeQueue(Q, q);
            cout << q->data << " ";
            if (q->lchild) {
                EnQueue(Q, q->lchild);
            }
            if (q->rchild) {
                EnQueue(Q, q->rchild);
            }
        }
        cout << endl;
        DestroyQueue(Q);
        return OK;
    }

    void CreateBiTree(BiTree &T, char*& pstr) {
        if (*pstr == '#') {
            T = nullptr;
        } else {
            T = (BiTree) malloc(sizeof(BiTNode));
            if (!T) exit(OVERFLOW);
            T->data = *pstr;
            CreateBiTree(T->lchild, ++pstr);
            CreateBiTree(T->rchild, ++pstr);
        }
    }
}

/*
using namespace sweetcookie6_1;

int main() {
    system("chcp 65001");
    BiTree T;
    InitBiTree(T);
    char *pstr = (char *) "abdg###e##c#f##";
//    char *pstr = (char *) "AB#D##C##";
    CreateBiTree(T, pstr);

    cout << "现在中序遍历二叉树" << endl;
    InOrderTraverseNoRecur(T);
    cout << "现在先序遍历二叉树" << endl;
    PreOrderTraverseNoRecur(T);
    cout << "现在层序遍历二叉树" << endl;
    LevelOrderTraverse(T);
//    cout << "跑起来再说" << endl;

    return 0;
}*/
